package org.aplombh.java.leetcode.all;

public class _10正则表达式匹配 {
    public static void main(String[] args) {
        System.out.println(new Solution10_2().isMatch("aab", "c*a*b"));
    }
}

class Solution10_1 {

    /*
        设主串s的长度为m,设模式串p的长度为n;其中s只有小写字母,p有字母/./*

        1.状态定义:dp[i][j]为考虑s[0,i-1]与p[0,j-1]是否能匹配上,能匹配上就为true

        2.状态转移:dp[i][j]<=s[i-1]与p[j-1]
            2.1 当p[j-1]=='.'时, s->,p->, dp[i][j] = dp[i-1][j-1]

            2.2 当p[j-1]=='a'-'z'时
                2.2.1 若s[i-1]==p[j-1]时,s->,p->,  dp[i][j] = dp[i-1][j-1]
                2.2.1 若s[i-1]!=p[j-1]时,s->,p->,  dp[i][j] = false
            2.3 当p[j-1]=='*'时
                2.3.1 p[j-2]=='.', s->,p-  dp[i][j]=dp[i-1][j]
                2.3.2 p[j-2]=='a'-'z'
                    2.3.2.1 p[j-2]==s[i-1], s->,p-,
                        2.3.2.1.1 a都取0次 dp[i][j] ||= dp[i][j-2]
                        2.3.2.1.1 a都取1次, dp[i][j] ||= dp[i][j-1] || dp[i-1][j]||dp[i-1][j-1]||dp[i-1][j-2]
                    2.3.2.2 p[j-2]!=s[i-1], s->,p->,  dp[i][j]=dp[i][j-2]

        3.初始化:
            3.1 空s,空p,  dp[0][0]=true
            3.2 空s,非空的p, -
            3.3 非空的s,空p, dp[i][0]=false,i∈[1,m]
            3.3 非空的s,非空的p, -
        4.遍历顺序:正序遍历
        5.返回形式:dp[m][n]
        */
    public boolean isMatch(String s, String p) {

        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        // 初始化
        dp[0][0] = true;


        for (int j = 1; j <= n; j++) {
            if (j == 1) {
                // s为空，p为* 匹配成功
                if ((p.charAt(0) == '*'))
                    dp[0][1] = true;
            }
            // 如果p为* 则可以当作不存在
            else if (p.charAt(j - 1) == '*')
                dp[0][j] = dp[0][j - 2];
        }

        // i从1开始
        for (int i = 1; i <= m; i++) {
            // 注意j从1开始
            for (int j = 1; j <= n; j++) {

                // 2.1
                if (p.charAt(j - 1) == '.')
                    dp[i][j] = dp[i - 1][j - 1];
                    // 2.2
                else if (p.charAt(j - 1) != '*') {
                    if ((i >= 1 && j >= 1) && (s.charAt(i - 1) == p.charAt(j - 1))) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
                // 2.3
                else {
                    // 2.3.1
                    if ((j >= 2 && i >= 1) && p.charAt(j - 2) == '.')
                        dp[i][j] = dp[i - 1][j];
                    // 2.3.2.1
                    if ((j >= 2 && i >= 1) && (p.charAt(j - 2) == s.charAt(i - 1))) {
                        dp[i][j] = dp[i][j - 1] || dp[i - 1][j] || dp[i - 1][j - 1] || dp[i - 1][j - 2];
                    }
                    // 2.3.2.2
                    if (j >= 2) {
                        dp[i][j] = dp[i][j] || dp[i][j - 2];
                    }
                }
            }
        }
        return dp[m][n];
    }
}


class Solution10_2 {
    public boolean isMatch(String s, String p) {

        s = " " + s;
        p = " " + p;

        char[] cs = s.toCharArray();
        char[] cp = p.toCharArray();

        int m = s.length(), n = p.length();

        boolean[][] dp = new boolean[m + 1][n + 1];

        dp[0][0] = true;

        // 考虑aa c*a* 的情况
        for (int i = 1; i < n; i++) {
            if (cp[i] == '*') dp[0][i] = dp[0][i - 2];
        }

        // i 表示s的位置
        // j 表示p的位置
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 匹配任意字符
                if (cp[j] == '.' || cs[i] == cp[j])
                    dp[i][j] = dp[i - 1][j - 1];
                else if (cp[j] == '*') {
                    // 匹配1次或者0次
                    dp[i][j] = dp[i][j - 1] || dp[i][j - 2];
                    if (cp[j - 1] == '.' || cp[j - 1] == cs[i]) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}